#include "stdio.h"
#include "time.h"
#include "stdlib.h"
void bubble(int len, int *a)
{
	int i,j,t,tmp;
	t = clock();
	for(i = 0; i < len-1; i++)
		for(j = 0; j < len-1; j++)
			if(a[j]	> a[j+1]) 
				{
					tmp = a[j];
					a[j] = a[j+1]; 
					a[j+1] = tmp;
				}
	printf("%s %d\n", "Bubble sorting time:", clock()-t); 
}

void good_bubble(int len, int *a)
{
	int i,j,t,tmp,flag;
	t = clock();
	for(i = 0; i < len-1; i++)
		{
			flag = 0;
			for(j = 0; j < len-i-1; j++)
				if(a[j]	> a[j+1]) 
					{
						tmp = a[j];
						a[j] = a[j+1];
						a[j+1] = tmp;
						flag = 1;
					}
			if (flag == 0) break;
		}
	printf("%s %d\n", "Good bubble sorting time:", clock()-t);
}

void shaker_bubble(int len, int *a)
{
	int i,left,t,right,tmp;
	t = clock();
	left = 0;
	right = len-1;
		for(; left <= right;left++)
		{
			for(i = left; i < right; i++)
				if(a[i]	> a[i+1]) 
					{
						tmp = a[i];
						a[i] = a[i+1];
						a[i+1] = tmp;
					}
			right--;
			for(i = right; i >= left; i--)
				if(a[i]	> a[i+1]) 
					{
						tmp = a[i];
						a[i] = a[i+1];
						a[i+1] = tmp;
					}
		}
	printf("%s %d\n", "Shaker bubble sorting time:", clock()-t);
}
int main()
{
	const int n=10;
	int i;
	int a[10],b[10],c[10];
	srand(time(NULL));
	
	for(i = 0; i<n ; i++) 
		{
			a[i] = rand()%1000;
			b[i] = a[i];
			c[i] = a[i];
			//printf("%d\t", a[i]);
		}
	printf("\n");
	bubble(n,a);
	// for(i = 0; i < n ; i++) 
		// printf("%d\t", a[i]);
	good_bubble(n,b);
	// for(i = 0; i < n ; i++) 
		// printf("%d\t", b[i]);
	shaker_bubble(n,c);
	// for(i = 0; i < n ; i++) 
		// printf("%d\t", c[i]);
	return 0;
}